package com.leetcode.partition6;

/**
 * @author `RKC`
 * @date 2021/10/25 19:03
 */
public class LC576出界的路径数 {

    private static final int MOD = 1000000007;
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        return dynamicProgramming(m, n, maxMove, startRow, startColumn);
    }

    public static void main(String[] args) {
        System.out.println(findPaths(2, 2, 2, 0, 0));
    }

    private static int dynamicProgramming(int m, int n, int maxMove, int startRow, int startColumn) {
        //dp[k][i][j]：球移动k次后位于坐标(i, j)的路径数量，如果(i, j)出界，就统计
        int[][][] dp = new int[maxMove + 1][m][n];
        //初始状态，起点必定是1
        dp[0][startRow][startColumn] = 1;
        int answer = 0;
        for (int k = 0; k < maxMove; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[k][i][j] == 0) continue;
                    for (int[] dir : dirs) {
                        int row = i + dir[0], col = j + dir[1];
                        //如果邻接点越界就进行统计数量，否则计算下一步路径的数量dp[k+1][row][col]+=dp[k][i][j]
                        if (row < 0 || row == m || col < 0 || col == n) {
                            answer = (answer + dp[k][i][j]) % MOD;
                        } else {
                            dp[k + 1][row][col] = (dp[k + 1][row][col] + dp[k][i][j]) % MOD;
                        }
                    }
                }
            }
        }
        return answer;
    }
}
